package com.sicheng.lc.周赛.分类.前缀和or差分数组;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/5 19:59
 */
public class 用邮票贴满网格图 {
    //https://leetcode.cn/problems/stamping-the-grid/

    int m, n;
    int[][] sum, d;

    public boolean possibleToStamp(int[][] grid, int h, int l) {
        init(grid);
        for (int i = 1; i <= m; i++) {
            if (i + h - 1 > m)
                break;
            for (int j = 1; j <= n; j++) {
                if (j + l - 1 > n)
                    break;
                if (preSum(i, j, i + h - 1, j + l - 1) > 0)
                    continue;
                insert(i, j, i + h - 1, j + l - 1, 1);
            }
        }


        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                d[i + 1][j + 1] = d[i + 1][j + 1] + d[i][j + 1] + d[i + 1][j] - d[i][j];
                if (d[i + 1][j + 1] == 0)
                    return false;
            }
        }
        return true;
    }


    int preSum(int x1, int y1, int x2, int y2) {
        return sum[x2][y2] + sum[x1 - 1][y1 - 1] - sum[x1 - 1][y2] - sum[x2][y1 - 1];
    }

    void insert(int x1, int y1, int x2, int y2, int m) {
        d[x1][y1] += m;
        d[x2 + 1][y2 + 1] += m;
        d[x2 + 1][y1] -= m;
        d[x1][y2 + 1] -= m;
    }

    private void init(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        sum = new int[m + 2][n + 2];
        d = new int[m + 2][n + 2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i + 1][j + 1] = grid[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
                insert(i + 1, j + 1, i + 1, j + 1, grid[i][j]);
            }
        }
    }

    public static void main(String[] args) {
        用邮票贴满网格图 s = new 用邮票贴满网格图();
        int[][] g = {{1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}};
        System.out.println(s.possibleToStamp(g, 4, 3));
    }
}
